#include <asm-i386/types.h>
#include <linux/list.h>
#include <asm-i386/page.h>
#include <asm-i386/cache.h>
#include <linux/slab.h>
#include <linux/spin_lock.h>
#include <linux/debug.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <asm-i386/stdio.h>
#define	SLAB_LIMIT 0xffffFFFE
#define cache_chain (cache_cache.next)
#define is_chained_kmem_cache(x) 1
/*
 * kmem_cache_t
 *
 * manages a cache.
 */

#define CACHE_NAMELEN	20	/* max name length for a slab cache */
/* Shouldn't this be in a header file somewhere? */
#define	BYTES_PER_WORD		sizeof(void *)

/* maximum size of an obj (in 2^order pages) */
#define	MAX_OBJ_ORDER	5	/* 32 pages */

#define	OFF_SLAB(x)	((x)->flags & CFLGS_OFF_SLAB)
#define	OPTIMIZE(x)	((x)->flags & CFLGS_OPTIMIZE)
#define	GROWN(x)	((x)->dlags & DFLGS_GROWN)
/*
 * Parameters for kmem_cache_reap
 */
#define REAP_SCANLEN	10
#define REAP_PERFECT	10

/*
 * Absolute limit for the gfp order
 */
#define	MAX_GFP_ORDER	5	/* 32 pages */
#define BUFCTL_END 0xffffFFFF
#define	SLAB_LIMIT 0xffffFFFE

/* Max number of objs-per-slab for caches which use off-slab slabs.
 * Needed to avoid a possible looping condition in kmem_cache_grow().
 */
static unsigned long offslab_limit;

/*
 * Do not go above this order unless 0 objects fit into the slab.
 */
#define	BREAK_GFP_ORDER_HI	2
#define	BREAK_GFP_ORDER_LO	1

/* Macros for storing/retrieving the cachep and or slab from the
 * global 'mem_map'. These are used to find the slab an obj belongs to.
 * With kfree(), these are used to find the cache which an obj belongs to.
 */
#define	SET_PAGE_CACHE(pg,x)  ((pg)->list.next = (struct list_head *)(x))
#define	GET_PAGE_CACHE(pg)    ((kmem_cache_t *)(pg)->list.next)
#define	SET_PAGE_SLAB(pg,x)   ((pg)->list.prev = (struct list_head *)(x))
#define	GET_PAGE_SLAB(pg)     ((slab_t *)(pg)->list.prev)
#define slab_bufctl(slabp) \
	((kmem_bufctl_t *)(((slab_t*)slabp)+1))
/* c_dflags (dynamic flags). Need to hold the spinlock to access this member */
#define	DFLGS_GROWN	0x000001UL	/* don't reap a recently grown */

static int slab_break_gfp_order = BREAK_GFP_ORDER_LO;

struct kmem_cache_s {
/* 1) each alloc & free */
    /* full, partial first, then free */
    struct list_head	slabs_full;
    struct list_head	slabs_partial;
    struct list_head	slabs_free;
    unsigned int		objsize;
    unsigned int	 	flags;	/* constant flags */
    unsigned int		num;	/* # of objs per slab */
    spinlock_t		spinlock;

/* 2) slab additions /removals */
    /* order of pgs per slab (2^n) */
    unsigned int		gfporder;

    /* force GFP flags, e.g. GFP_DMA */
    unsigned int		gfpflags;

    size_t			colour;		/* cache colouring range */
    unsigned int		colour_off;	/* colour offset */
    unsigned int		colour_next;	/* cache colouring */
    kmem_cache_t		*slabp_cache;
    unsigned int		growing;
    unsigned int		dflags;		/* dynamic flags */

    /* constructor func */
    void (*ctor)(void *, kmem_cache_t *, unsigned long);

    /* de-constructor func */
    void (*dtor)(void *, kmem_cache_t *, unsigned long);

    unsigned long		failures;

/* 3) cache creation/removal */
    char			name[CACHE_NAMELEN];
    struct list_head	next;
};

/* internal cache of cache description objs */
static kmem_cache_t cache_cache = {
        slabs_full:	LIST_HEAD_INIT(cache_cache.slabs_full),
        slabs_partial:	LIST_HEAD_INIT(cache_cache.slabs_partial),
        slabs_free:	LIST_HEAD_INIT(cache_cache.slabs_free),
        objsize:	sizeof(kmem_cache_t),
        flags:		SLAB_NO_REAP,
        spinlock:	SPIN_LOCK_UNLOCKED,
        colour_off:	L1_CACHE_BYTES,
        name:		"kmem_cache",
};
typedef unsigned int kmem_bufctl_t;
/* Place maintainer for reaping. */
static kmem_cache_t *clock_searchp = &cache_cache;

/* Size description struct for general caches. */
typedef struct cache_sizes {
    size_t		 cs_size;
    kmem_cache_t	*cs_cachep;
    kmem_cache_t	*cs_dmacachep;
} cache_sizes_t;

static cache_sizes_t cache_sizes[] = {
#if PAGE_SIZE == 4096
        {    32,	NULL, NULL},
#endif
        {    64,	NULL, NULL},
        {   128,	NULL, NULL},
        {   256,	NULL, NULL},
        {   512,	NULL, NULL},
        {  1024,	NULL, NULL},
        {  2048,	NULL, NULL},
        {  4096,	NULL, NULL},
        {  8192,	NULL, NULL},
        { 16384,	NULL, NULL},
        { 32768,	NULL, NULL},
        { 65536,	NULL, NULL},
        {131072,	NULL, NULL},
        {     0,	NULL, NULL}
};

/*
 * slab_t
 *
 * Manages the objs in a slab. Placed either at the beginning of mem allocated
 * for a slab, or allocated from an general cache.
 * Slabs are chained into three list: fully used, partial, fully free slabs.
 */
typedef struct slab_s {
    struct list_head	list;
    unsigned long		colouroff;
    void			*s_mem;		/* including colour offset */
    unsigned int		inuse;		/* num of objs active in slab */
    kmem_bufctl_t		free;
} slab_t;

/* internal c_flags */
#define	CFLGS_OFF_SLAB	0x010000UL	/* slab management in own cache */
#define	CFLGS_OPTIMIZE	0x020000UL	/* optimized slab lookup */

static inline void * kmem_cache_alloc_one_tail (kmem_cache_t *cachep,
                                                slab_t *slabp)
{
    void *objp;
    /* get obj pointer */
    slabp->inuse++;
    objp = slabp->s_mem + slabp->free*cachep->objsize;
    slabp->free=slab_bufctl(slabp)[slabp->free];

    if (slabp->free == BUFCTL_END) {
        list_del(&slabp->list);
        list_add(&slabp->list, &cachep->slabs_full);
    }
    return objp;
}

/*
 * Returns a ptr to an obj in the given cache.
 * caller must guarantee synchronization
 * #define for the goto optimization 8-)
 */
#define kmem_cache_alloc_one(cachep)				\
({								\
	struct list_head * slabs_partial, * entry;		\
	slab_t *slabp;						\
								\
	slabs_partial = &(cachep)->slabs_partial;		\
	entry = slabs_partial->next;				\
	if (entry == slabs_partial) {			\
		struct list_head * slabs_free;			\
		slabs_free = &(cachep)->slabs_free;		\
		entry = slabs_free->next;			\
		if (entry == slabs_free)		\
			goto alloc_new_slab;			\
		list_del(entry);				\
		list_add(entry, slabs_partial);			\
	}							\
								\
	slabp = list_entry(entry, slab_t, list);		\
	kmem_cache_alloc_one_tail(cachep, slabp);		\
})

static void kmem_cache_estimate (unsigned long gfporder, size_t size,
                                 int flags, size_t *left_over, unsigned int *num)
{
    int i;
    size_t wastage = PAGE_SIZE<<gfporder;
    size_t extra = 0;
    size_t base = 0;

    if (!(flags & CFLGS_OFF_SLAB)) {
        base = sizeof(slab_t);
        extra = sizeof(kmem_bufctl_t);
    }
    i = 0;
    while (i*size + L1_CACHE_ALIGN(base+i*extra) <= wastage)
        i++;
    if (i > 0)
        i--;

    if (i > SLAB_LIMIT)
        i = SLAB_LIMIT;

    *num = i;
    wastage -= i*size;
    wastage -= L1_CACHE_ALIGN(base+i*extra);
    *left_over = wastage;
}

/* Initialisation - setup the `cache' cache. */
void kmem_cache_init(void)
{
    size_t left_over;


    //init_MUTEX(&cache_chain_sem);
    INIT_LIST_HEAD(&cache_chain);

    kmem_cache_estimate(0, cache_cache.objsize, 0,
                        &left_over, &cache_cache.num);
    if (!cache_cache.num)
        BUG();

    cache_cache.colour = left_over/cache_cache.colour_off;
    cache_cache.colour_next = 0;
}

kmem_cache_t *
kmem_cache_create (const char *name, size_t size, size_t offset,
                   unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
                   void (*dtor)(void*, kmem_cache_t *, unsigned long))//name:高速缓存的可读名，size:对象的大小,offset:对象的边界，一般设置为0,flags:静态高速缓存标志位
{
    size_t left_over, align, slab_size;
    kmem_cache_t *cachep = NULL;

    /*
     * Sanity checks... these are all serious usage bugs.
     */
    if ((!name) ||
        ((strlen(name) >= CACHE_NAMELEN - 1)) ||
        //in_interrupt() ||
        (size < BYTES_PER_WORD) ||
        (size > (1<<MAX_OBJ_ORDER)*PAGE_SIZE) ||
        (dtor && !ctor) ||
        (offset < 0 || offset > size))
        BUG();

    /* Get cache's description obj. */
    cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
    if (!cachep)
        goto opps;
    memset(cachep, 0, sizeof(kmem_cache_t));

    /* Check that size is in terms of words.  This is needed to avoid
     * unaligned accesses for some archs when redzoning is used, and makes
     * sure any on-slab bufctl's are also correctly aligned.
     */
    if (size & (BYTES_PER_WORD-1)) {
        size += (BYTES_PER_WORD-1);
        size &= ~(BYTES_PER_WORD-1);
    }


    align = BYTES_PER_WORD;
    if (flags & SLAB_HWCACHE_ALIGN)
        align = L1_CACHE_BYTES;

    /* Determine if the slab management is 'on' or 'off' slab. */
    if (size >= (PAGE_SIZE>>3))
        /*
         * Size is large, assume best to place the slab management obj
         * off-slab (should allow better packing of objs).
         */
        flags |= CFLGS_OFF_SLAB;

    if (flags & SLAB_HWCACHE_ALIGN) {
        /* Need to adjust size so that objs are cache aligned. */
        /* Small obj size, can get at least two per cache line. */
        /* FIXME: only power of 2 supported, was better */
        while (size < align/2)
            align /= 2;
        size = (size+align-1)&(~(align-1));
    }

    /* Cal size (in pages) of slabs, and the num of objs per slab.
     * This could be made much more intelligent.  For now, try to avoid
     * using high page-orders for slabs.  When the gfp() funcs are more
     * friendly towards high-order requests, this should be changed.
     */
    do {
        unsigned int break_flag = 0;
        cal_wastage:
        kmem_cache_estimate(cachep->gfporder, size, flags,
                            &left_over, &cachep->num);
        if (break_flag)
            break;
        if (cachep->gfporder >= MAX_GFP_ORDER)
            break;
        if (!cachep->num)
            goto next;
        if (flags & CFLGS_OFF_SLAB && cachep->num > offslab_limit) {
            /* Oops, this num of objs will cause problems. */
            cachep->gfporder--;
            break_flag++;
            goto cal_wastage;
        }

        /*
         * Large num of objs is good, but v. large slabs are currently
         * bad for the gfp()s.
         */
        if (cachep->gfporder >= slab_break_gfp_order)
            break;

        if ((left_over*8) <= (PAGE_SIZE<<cachep->gfporder))
            break;	/* Acceptable internal fragmentation. */
        next:
        cachep->gfporder++;
    } while (1);

    if (!cachep->num) {
        kmem_cache_free(&cache_cache, cachep);
        cachep = NULL;
        goto opps;
    }
    slab_size = L1_CACHE_ALIGN(cachep->num*sizeof(kmem_bufctl_t)+sizeof(slab_t));

    /*
     * If the slab has been placed off-slab, and we have enough space then
     * move it on-slab. This is at the expense of any extra colouring.
     */
    if (flags & CFLGS_OFF_SLAB && left_over >= slab_size) {
        flags &= ~CFLGS_OFF_SLAB;
        left_over -= slab_size;
    }

    /* Offset must be a multiple of the alignment. */
    offset += (align-1);
    offset &= ~(align-1);
    if (!offset)
        offset = L1_CACHE_BYTES;
    cachep->colour_off = offset;
    cachep->colour = left_over/offset;

    /* init remaining fields */
    if (!cachep->gfporder && !(flags & CFLGS_OFF_SLAB))
        flags |= CFLGS_OPTIMIZE;

    cachep->flags = flags;//设置高速缓存静态标志位
    cachep->gfpflags = 0;
    if (flags & SLAB_CACHE_DMA)
        cachep->gfpflags |= GFP_DMA;//如果设置了该标志位，伙伴分配器将使用ZONE_DMA
    spin_lock_init(&cachep->spinlock);
    cachep->objsize = size;
    INIT_LIST_HEAD(&cachep->slabs_full);
    INIT_LIST_HEAD(&cachep->slabs_partial);
    INIT_LIST_HEAD(&cachep->slabs_free);

//    if (flags & CFLGS_OFF_SLAB)
//        cachep->slabp_cache = kmem_find_general_cachep(slab_size,0);
    cachep->ctor = ctor;
    cachep->dtor = dtor;
    /* Copy name over so we don't have problems with unloaded modules */
    strcpy(cachep->name, name);

    /* Need the semaphore to access the chain. */
    //down(&cache_chain_sem);
    {
        struct list_head *p;

        list_for_each(p, &cache_chain) {
            kmem_cache_t *pc = list_entry(p, kmem_cache_t, next);

            /* The name field is constant - no lock needed. */
            if (!strcmp(pc->name, name))
                BUG();
        }
    }

    /* There is no reason to lock our new cache before we
     * link it in - no one knows about it yet...
     */
    list_add(&cachep->next, &cache_chain);
    //up(&cache_chain_sem);
    opps:
    return cachep;
}

/* Initialisation - setup remaining internal and general caches.
 * Called after the gfp() functions have been enabled, and before smp_init().
 */
void  kmem_cache_sizes_init(void)
{
    cache_sizes_t *sizes = cache_sizes;
    char name[20];
    /*
     * Fragmentation resistance on low memory - only use bigger
     * page orders on machines with more than 32MB of memory.
     */
    if (num_physpages > (32 << 20) >> PAGE_SHIFT)
        slab_break_gfp_order = BREAK_GFP_ORDER_HI;
    do {
        /* For performance, all the general caches are L1 aligned.
         * This should be particularly beneficial on SMP boxes, as it
         * eliminates "false sharing".
         * Note for systems short on memory removing the alignment will
         * allow tighter packing of the smaller caches. */
        sprintf(name, "size-%Zd",sizes->cs_size);
        sizes->cs_cachep =kmem_cache_create(name, sizes->cs_size,0, SLAB_HWCACHE_ALIGN, NULL, NULL);
        if (!sizes->cs_cachep) {
            BUG();
        }

        /* Inc off-slab bufctl limit until the ceiling is hit. */
        if (!(OFF_SLAB(sizes->cs_cachep))) {
            offslab_limit = sizes->cs_size-sizeof(slab_t);
            offslab_limit /= 2;
        }
        sprintf(name, "size-%Zd(DMA)",sizes->cs_size);
        sizes->cs_dmacachep = kmem_cache_create(name, sizes->cs_size, 0,
                                                SLAB_CACHE_DMA|SLAB_HWCACHE_ALIGN, NULL, NULL);
        if (!sizes->cs_dmacachep)
            BUG();
        sizes++;
    } while (sizes->cs_size);
}

/* Interface to system's page release. */
static inline void kmem_freepages (kmem_cache_t *cachep, void *addr)
{
    unsigned long i = (1<<cachep->gfporder);
    struct page *page = virt_to_page(addr);

    /* free_pages() does not clear the type bit - we do that.
     * The pages have been unlinked from their cache-slab,
     * but their 'struct page's might be accessed in
     * vm_scan(). Shouldn't be a worry.
     */
    while (i--) {
        PageClearSlab(page);
        page++;
    }
    free_pages((unsigned long)addr, cachep->gfporder);
}

static inline void kmem_cache_free_one(kmem_cache_t *cachep, void *objp)
{
    slab_t* slabp;

    /* reduces memory footprint
     *
    if (OPTIMIZE(cachep))
        slabp = (void*)((unsigned long)objp&(~(PAGE_SIZE-1)));
     else
     */
    slabp = GET_PAGE_SLAB(virt_to_page(objp));

    {
        unsigned int objnr = (objp-slabp->s_mem)/cachep->objsize;
        slab_bufctl(slabp)[objnr] = slabp->free;
        slabp->free = objnr;
    }

    /* fixup slab chains */
    {
        int inuse = slabp->inuse;
        if (!--slabp->inuse) {
            /* Was partial or full, now empty. */
            list_del(&slabp->list);
            list_add(&slabp->list, &cachep->slabs_free);
        } else if (inuse == cachep->num) {
            /* Was full. */
            list_del(&slabp->list);
            list_add(&slabp->list, &cachep->slabs_partial);
        }
    }
}

/*
 * __kmem_cache_free
 * called with disabled ints
 */
static inline void __kmem_cache_free (kmem_cache_t *cachep, void* objp)
{
    kmem_cache_free_one(cachep, objp);
}

/**
 * kmem_cache_free - Deallocate an object
 * @cachep: The cache the allocation was from.
 * @objp: The previously allocated object.
 *
 * Free an object which was previously allocated from this
 * cache.
 */
void kmem_cache_free (kmem_cache_t *cachep, void *objp)
{
    unsigned long flags;

    local_irq_save(flags);
    __kmem_cache_free(cachep, objp);
    local_irq_restore(flags);
}

/* Destroy all the objs in a slab, and release the mem back to the system.
 * Before calling the slab must have been unlinked from the cache.
 * The cache-lock is not held/needed.
 */
static void kmem_slab_destroy (kmem_cache_t *cachep, slab_t *slabp)
{
    if (cachep->dtor) {
        int i;
        for (i = 0; i < cachep->num; i++) {
            void* objp = slabp->s_mem+cachep->objsize*i;
            if (cachep->dtor)
                (cachep->dtor)(objp, cachep, 0);
        }
    }

    kmem_freepages(cachep, slabp->s_mem-slabp->colouroff);
    if (OFF_SLAB(cachep))
        kmem_cache_free(cachep->slabp_cache, slabp);
}

/*
 * Called with the &cachep->spinlock held, returns number of slabs released
 */
static int __kmem_cache_shrink_locked(kmem_cache_t *cachep)
{
    slab_t *slabp;
    int ret = 0;

    /* If the cache is growing, stop shrinking. */
    while (!cachep->growing) {
        struct list_head *p;

        p = cachep->slabs_free.prev;
        if (p == &cachep->slabs_free)
            break;

        slabp = list_entry(cachep->slabs_free.prev, slab_t, list);

        list_del(&slabp->list);

        spin_unlock_irq(&cachep->spinlock);
        kmem_slab_destroy(cachep, slabp);
        ret++;
        spin_lock_irq(&cachep->spinlock);
    }
    return ret;
}

static int __kmem_cache_shrink(kmem_cache_t *cachep)
{
    int ret;

    spin_lock_irq(&cachep->spinlock);
    __kmem_cache_shrink_locked(cachep);
    ret = !list_empty(&cachep->slabs_full) ||
          !list_empty(&cachep->slabs_partial);
    spin_unlock_irq(&cachep->spinlock);
    return ret;
}


/**
 * kmem_cache_shrink - Shrink a cache.
 * @cachep: The cache to shrink.
 *
 * Releases as many slabs as possible for a cache.
 * Returns number of pages released.
 */
int kmem_cache_shrink(kmem_cache_t *cachep)
{
    int ret;

    if (!cachep ||
    //in_interrupt() ||
    !is_chained_kmem_cache(cachep))
        BUG();

    spin_lock_irq(&cachep->spinlock);
    ret = __kmem_cache_shrink_locked(cachep);
    spin_unlock_irq(&cachep->spinlock);

    return ret << cachep->gfporder;
}

/**
 * kmem_cache_destroy - delete a cache
 * @cachep: the cache to destroy
 *
 * Remove a kmem_cache_t object from the slab cache.
 * Returns 0 on success.
 *
 * It is expected this function will be called by a module when it is
 * unloaded.  This will remove the cache completely, and avoid a duplicate
 * cache being allocated each time a module is loaded and unloaded, if the
 * module doesn't have persistent in-kernel storage across loads and unloads.
 *
 * The cache must be empty before calling this function.
 *
 * The caller must guarantee that noone will allocate memory from the cache
 * during the kmem_cache_destroy().
 */
int kmem_cache_destroy (kmem_cache_t * cachep)
{
    if (!cachep ||
    //in_interrupt() ||
    cachep->growing)
        BUG();

    /* Find the cache in the chain of caches. */
    //down(&cache_chain_sem);
    /* the chain is never empty, cache_cache is never destroyed */
    if (clock_searchp == cachep)
        clock_searchp = list_entry(cachep->next.next,
                                   kmem_cache_t, next);
    list_del(&cachep->next);
    //up(&cache_chain_sem);

    if (__kmem_cache_shrink(cachep)) {
        printk("kmem_cache_destroy: Can't free all objects %p\n",
                cachep);
        //down(&cache_chain_sem);
        list_add(&cachep->next,&cache_chain);
        //up(&cache_chain_sem);
        return 1;
    }
    kmem_cache_free(&cache_cache, cachep);

    return 0;
}

/**
 * kmem_cache_reap - Reclaim memory from caches.
 * @gfp_mask: the type of memory required.
 *
 * Called from do_try_to_free_pages() and __alloc_pages()
 */
int kmem_cache_reap (int gfp_mask)
{
    slab_t *slabp;
    kmem_cache_t *searchp;
    kmem_cache_t *best_cachep;
    unsigned int best_pages;
    unsigned int best_len;
    unsigned int scan;
    int ret = 0;

//    if (gfp_mask & __GFP_WAIT)
//        down(&cache_chain_sem);
//    else
//    if (down_trylock(&cache_chain_sem))
//        return 0;

    scan = REAP_SCANLEN;
    best_len = 0;
    best_pages = 0;
    best_cachep = NULL;
    searchp = clock_searchp;
    do {
        unsigned int pages;
        struct list_head* p;
        unsigned int full_free;

        /* It's safe to test this without holding the cache-lock. */
        if (searchp->flags & SLAB_NO_REAP)
            goto next;
        spin_lock_irq(&searchp->spinlock);
        if (searchp->growing)
            goto next_unlock;
        if (searchp->dflags & DFLGS_GROWN) {
            searchp->dflags &= ~DFLGS_GROWN;
            goto next_unlock;
        }

        full_free = 0;
        p = searchp->slabs_free.next;
        while (p != &searchp->slabs_free) {
            slabp = list_entry(p, slab_t, list);
            full_free++;
            p = p->next;
        }

        /*
         * Try to avoid slabs with constructors and/or
         * more than one page per slab (as it can be difficult
         * to get high orders from gfp()).
         */
        pages = full_free * (1<<searchp->gfporder);
        if (searchp->ctor)
            pages = (pages*4+1)/5;
        if (searchp->gfporder)
            pages = (pages*4+1)/5;
        if (pages > best_pages) {
            best_cachep = searchp;
            best_len = full_free;
            best_pages = pages;
            if (pages >= REAP_PERFECT) {
                clock_searchp = list_entry(searchp->next.next,
                                           kmem_cache_t,next);
                goto perfect;
            }
        }
next_unlock:
        spin_unlock_irq(&searchp->spinlock);
next:
        searchp = list_entry(searchp->next.next,kmem_cache_t,next);
    } while (--scan && searchp != clock_searchp);

    clock_searchp = searchp;

    if (!best_cachep)
        /* couldn't find anything to reap */
        goto out;

    spin_lock_irq(&best_cachep->spinlock);
perfect:
    /* free only 50% of the free slabs */
    best_len = (best_len + 1)/2;
    for (scan = 0; scan < best_len; scan++) {
        struct list_head *p;

        if (best_cachep->growing)
            break;
        p = best_cachep->slabs_free.prev;
        if (p == &best_cachep->slabs_free)
            break;
        slabp = list_entry(p,slab_t,list);
        list_del(&slabp->list);

        /* Safe to drop the lock. The slab is no longer linked to the
         * cache.
         */
        spin_unlock_irq(&best_cachep->spinlock);
        kmem_slab_destroy(best_cachep, slabp);
        spin_lock_irq(&best_cachep->spinlock);
    }
    spin_unlock_irq(&best_cachep->spinlock);
    ret = scan * (1 << best_cachep->gfporder);
    out:
    //up(&cache_chain_sem);
    return ret;
}


/* Get the memory for a slab management obj. */
static inline slab_t * kmem_cache_slabmgmt (kmem_cache_t *cachep,
                                            void *objp, int colour_off, int local_flags)
{
    slab_t *slabp;

    if (OFF_SLAB(cachep)) {
        /* Slab management obj is off-slab. */
        slabp = kmem_cache_alloc(cachep->slabp_cache, local_flags);
        if (!slabp)
            return NULL;
    } else {
        /* FIXME: change to
            slabp = objp
         * if you enable OPTIMIZE
         */
        slabp = objp+colour_off;
        colour_off += L1_CACHE_ALIGN(cachep->num *
                                     sizeof(kmem_bufctl_t) + sizeof(slab_t));
    }
    slabp->inuse = 0;
    slabp->colouroff = colour_off;
    slabp->s_mem = objp+colour_off;

    return slabp;
}

/* Interface to system's page allocator. No need to hold the cache-lock.
 */
static inline void * kmem_getpages (kmem_cache_t *cachep, unsigned long flags)
{
    void	*addr;

    /*
     * If we requested dmaable memory, we will get it. Even if we
     * did not request dmaable memory, we might get it, but that
     * would be relatively rare and ignorable.
     */
    flags |= cachep->gfpflags;
    addr = (void*) __get_free_pages(flags, cachep->gfporder);
    /* Assume that now we have the pages no one else can legally
     * messes with the 'struct page's.
     * However vm_scan() might try to test the structure to see if
     * it is a named-page or buffer-page.  The members it tests are
     * of no interest here.....
     */
    return addr;
}

static inline void kmem_cache_init_objs (kmem_cache_t * cachep,
                                         slab_t * slabp, unsigned long ctor_flags)
{
    int i;

    for (i = 0; i < cachep->num; i++) {
        void* objp = slabp->s_mem+cachep->objsize*i;
        /*
         * Constructors are not allowed to allocate memory from
         * the same cache which they are a constructor for.
         * Otherwise, deadlock. They must also be threaded.
         */
        if (cachep->ctor)
            cachep->ctor(objp, cachep, ctor_flags);
        slab_bufctl(slabp)[i] = i+1;
    }
    slab_bufctl(slabp)[i-1] = BUFCTL_END;
    slabp->free = 0;
}

/*
 * Grow (by 1) the number of slabs within a cache.  This is called by
 * kmem_cache_alloc() when there are no active objs left in a cache.
 */
static int kmem_cache_grow (kmem_cache_t * cachep, int flags)
{
    slab_t	*slabp;
    struct page	*page;
    void		*objp;
    size_t		 offset;
    unsigned int	 i, local_flags;
    unsigned long	 ctor_flags;
    unsigned long	 save_flags;

    /* Be lazy and only check for valid flags here,
      * keeping it out of the critical path in kmem_cache_alloc().
     */
    if (flags & ~(SLAB_DMA|SLAB_LEVEL_MASK|SLAB_NO_GROW))
        BUG();
    if (flags & SLAB_NO_GROW)
        return 0;

    /*
     * The test for missing atomic flag is performed here, rather than
     * the more obvious place, simply to reduce the critical path length
     * in kmem_cache_alloc(). If a caller is seriously mis-behaving they
     * will eventually be caught here (where it matters).
     */
//    if (in_interrupt() && (flags & SLAB_LEVEL_MASK) != SLAB_ATOMIC)
//        BUG();

    ctor_flags = SLAB_CTOR_CONSTRUCTOR;
    local_flags = (flags & SLAB_LEVEL_MASK);
    if (local_flags == SLAB_ATOMIC)
        /*
         * Not allowed to sleep.  Need to tell a constructor about
         * this - it might need to know...
         */
        ctor_flags |= SLAB_CTOR_ATOMIC;

    /* About to mess with non-constant members - lock. */
    spin_lock_irqsave(&cachep->spinlock, save_flags);

    /* Get colour for the slab, and cal the next value. */
    offset = cachep->colour_next;
    cachep->colour_next++;
    if (cachep->colour_next >= cachep->colour)
        cachep->colour_next = 0;
    offset *= cachep->colour_off;
    cachep->dflags |= DFLGS_GROWN;

    cachep->growing++;
    spin_unlock_irqrestore(&cachep->spinlock, save_flags);

    /* A series of memory allocations for a new slab.
     * Neither the cache-chain semaphore, or cache-lock, are
     * held, but the incrementing c_growing prevents this
     * cache from being reaped or shrunk.
     * Note: The cache could be selected in for reaping in
     * kmem_cache_reap(), but when the final test is made the
     * growing value will be seen.
     */

    /* Get mem for the objs. */
    if (!(objp = kmem_getpages(cachep, flags)))
        goto failed;

    /* Get slab management. */
    if (!(slabp = kmem_cache_slabmgmt(cachep, objp, offset, local_flags)))
        goto opps1;

    /* Nasty!!!!!! I hope this is OK. */
    i = 1 << cachep->gfporder;
    page = virt_to_page(objp);
    do {
        SET_PAGE_CACHE(page, cachep);
        SET_PAGE_SLAB(page, slabp);
        PageSetSlab(page);
        page++;
    } while (--i);

    kmem_cache_init_objs(cachep, slabp, ctor_flags);

    spin_lock_irqsave(&cachep->spinlock, save_flags);
    cachep->growing--;

    /* Make slab active. */
    list_add_tail(&slabp->list, &cachep->slabs_free);
    cachep->failures = 0;

    spin_unlock_irqrestore(&cachep->spinlock, save_flags);
    return 1;
opps1:
    kmem_freepages(cachep, objp);
failed:
    spin_lock_irqsave(&cachep->spinlock, save_flags);
    cachep->growing--;
    spin_unlock_irqrestore(&cachep->spinlock, save_flags);
    return 0;
}

static inline void kmem_cache_alloc_head(kmem_cache_t *cachep, int flags)
{
    if (flags & SLAB_DMA) {
        if (!(cachep->gfpflags & GFP_DMA))
            BUG();
    } else {
        if (cachep->gfpflags & GFP_DMA)
            BUG();
    }
}

static inline void * __kmem_cache_alloc (kmem_cache_t *cachep, int flags)
{
    unsigned long save_flags;
    void* objp;

    kmem_cache_alloc_head(cachep, flags);
try_again:
    //local_irq_save(save_flags);
    objp = kmem_cache_alloc_one(cachep);
   // local_irq_restore(save_flags);
    return objp;
alloc_new_slab:
    //local_irq_restore(save_flags);
    if (kmem_cache_grow(cachep, flags))
        /* Someone may have stolen our objs.  Doesn't matter, we'll
         * just come back here again.
         */
        goto try_again;
    return NULL;
}

/**
 * kmem_cache_alloc - Allocate an object
 * @cachep: The cache to allocate from.
 * @flags: See kmalloc().
 *
 * Allocate an object from this cache.  The flags are only relevant
 * if the cache has no available objects.
 */
void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)
{
    return __kmem_cache_alloc(cachep, flags);
}

kmem_cache_t * kmem_find_general_cachep (size_t size, int gfpflags)
{
    cache_sizes_t *csizep = cache_sizes;

    /* This function could be moved to the header file, and
     * made inline so consumers can quickly determine what
     * cache pointer they require.
     */
    for ( ; csizep->cs_size; csizep++) {
        if (size > csizep->cs_size)
            continue;
        break;
    }
    return (gfpflags & GFP_DMA) ? csizep->cs_dmacachep : csizep->cs_cachep;
}

